Multicomputer or parallel computer systems have been retarded in their use and application by limitations in systems for interconnecting and exchanging messages between the processors and the memories connected to the nodes of such systems. Interconnection networks have been very costly. It has been estimated that at least half the cost of a parallel computer system is in the area of interconnection. Parallel computer systems which have been available do not utilize more than a small number of computers due to the inability to efficiently communicate messages via their interconnection network.
In order to avoid message collisions during routing of multiple messages concurrently, conventional switching systems have buffers in each network node in which queues of messages awaiting transmission are stored. Flow control mechanisms are used in the network nodes to inform neighboring nodes of overflow conditions. Such systems then develop congestion in areas of the network, known as "hot spots" which can propagate through the network causing bottle neck and even deadlock in which message flow ceases because critical message queues are filled. When a bottleneck appears, the delay time in which a message remains in the network without reaching its destination can increase without bounds.
Techniques for message switching where the message is transmitted from node to node in its entirety and circuit switching in which a message header is sent from the source node to establish a fixed path to the destination node which is held between the source and destination nodes for as long as communication is taking place between the two nodes, have heretofore given rise to bottlenecks and deadlocks. Attempts to avoid bottlenecks and deadlocks have been based upon sorting of buffer space. See, P. Merlin and P.J. Schweitzer, "Deadlock Avoidance in Store and Forward Networks--I: Stored-And Forward", IEEE Transactions on Communications, COM 28-3 1988, pp. 345-354. A strategy in which acyclic message paths are used has been proposed as another way of avoiding deadlocks. See, W.J. Dally and C.L. Seitz, "Deadlock Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transactions on Computers, C36-5, May 1987, pp. 547-553. Such routing techniques are basically static, rather than dynamic since the route is determined at the initiation point (the source node).